/*
 *https://leetcode.cn/problems/jump-game-iii/description/
 *lc1306. 跳跃游戏 III
 *medium 吴朝泽 2024.12.3
 *BFS广度优先搜索
*/

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int len = arr.size();
        queue<int> Q;
        int vis[50001];    // 标记数组
        memset(vis, 0, sizeof(vis));

        Q.push(start);
        vis[start] = 1;

        while(!Q.empty()) 
        {
            int t = Q.front();  // 获取队列头位置

            // 如果当前的位置值为 0，返回 true
            if (arr[t] == 0) 
                return true;
            
            // 向左跳跃 t + arr[t]
            int left = t + arr[t];
            if (left < len && !vis[left]) 
            {
                Q.push(left);
                vis[left] = 1;
            }

            // 向右跳跃 t - arr[t]
            int right = t - arr[t];
            if (right >= 0 && !vis[right]) 
            {
                Q.push(right);
                vis[right] = 1;
            }
            Q.pop();
        }
        return false;
    }
};
